package com.itheima.leetcode.od.b.stack;

import java.util.LinkedList;

/**
 * (B卷,200分)- 仿LISP运算（Java & JS & Python）
 * <p>
 * 题目描述
 * <p>
 * LISP 语言唯一的语法就是括号要配对。
 * <p>
 * 形如 (OP P1 P2 …)，括号内元素由单个空格分割。
 * <p>
 * 其中第一个元素 OP 为操作符，后续元素均为其参数，参数个数取决于操作符类型。
 * <p>
 * 注意：
 * <p>
 * 参数 P1, P2 也有可能是另外一个嵌套的 (OP P1 P2 …) ，当前 OP 类型为 add / sub / mul / div（全小写），分别代表整数的加减乘除法，简单起见，所有 OP 参数个数均为 2 。
 * <p>
 * 举例：
 * <p>
 * 输入：(mul 3 -7)输出：-21
 * <p>
 * 输入：(add 1 2) 输出：3
 * <p>
 * 输入：(sub (mul 2 4) (div 9 3)) 输出 ：5
 * <p>
 * 输入：(div 1 0) 输出：error
 * <p>
 * 题目涉及数字均为整数，可能为负；
 * <p>
 * 不考虑 32 位溢出翻转，计算过程中也不会发生 32 位溢出翻转，
 * <p>
 * 除零错误时，输出 “error”，
 * <p>
 * 除法遇除不尽，向下取整，即 3/2 = 1
 * <p>
 * 输入描述
 * <p>
 * 输入为长度不超过512的字符串，用例保证了无语法错误
 * <p>
 * 输出描述
 * <p>
 * 输出计算结果或者“error”
 * <p>
 * 用例
 * <p>
 * 输入
 * (div 12 (sub 45 45))
 * 输出	error
 * 说明	45减45得0，12除以0为除零错误，输出error
 * <p>
 * 输入	(add 1 (div -7 3))
 * 输出	-2
 * 说明	-7除以3向下取整得-3，1加-3得-2
 * <p>
 * 题目解析
 * <p>
 * 纯逻辑题，难点在于将括号中的片段截取出来，我的处理方案是，遍历输入的每一个字符，当遇到")"时，则在其前面必然存在一个“(”，找到其前面第一个“(”，然后截取“(”和")"之间的内容（从栈中截取走），进行计算，将结果回填如栈中。
 */
public class ImitateLISP {
    public static void main(String[] args) {
        /*Scanner sc = new Scanner(System.in);*/

        System.out.println(getResult("(div 12 (sub 45 45))"));
    }

    private static LinkedList<Integer> stack = new LinkedList<>();

    /**
     * 采用逆波兰表达式（又叫后缀表达式）求解
     *
     * @param s
     * @return
     */
    public static String getResult(String s) {
        String lisp_str = s.replaceAll("\\(", "( ").replaceAll("\\)", " )").replaceAll("\\)\\(", ") (");
        String[] lisp_params = lisp_str.split(" ");

        LinkedList<String> suffixStack = new LinkedList<>();

        for (int i = 0; i < lisp_params.length; i++) {
            //分支判定各字符
            String param = lisp_params[i];
            switch (param) {
                case "add", "sub", "mul", "div" -> {
                    if (suffixStack.isEmpty()) {
                        suffixStack.push(param);
                    } else {
                        if (priority(param) > priority(suffixStack.peek())) {
                            suffixStack.push(param);
                        } else {
                            while (!suffixStack.isEmpty() && priority(suffixStack.peek()) >= priority(param)) {
                                if (!evalRPN(suffixStack.pop())) {
                                    return "error";
                                }
                            }
                            suffixStack.push(param);
                        }
                    }
                }
                case "(" -> {
                    suffixStack.push(param);
                }
                case ")" -> {
                    while (!suffixStack.isEmpty() && !suffixStack.peek().equals("(")) {
                        if (!evalRPN(suffixStack.pop())) {
                            return "error";
                        }
                    }
                    suffixStack.pop();
                }
                default -> {
                    evalRPN(param);
                }
            }
        }

        // 收尾操作
        while (!suffixStack.isEmpty()) {
            if (!evalRPN(suffixStack.pop())) {
                return "error";
            }
        }
        return String.valueOf(stack.pop());
    }

    public static boolean evalRPN(String t) {
        boolean flag = true;
        switch (t) {
            case "add" -> {
                Integer b = stack.pop();
                Integer a = stack.pop();
                stack.push(a + b);
            }
            case "sub" -> {
                Integer b = stack.pop();
                Integer a = stack.pop();
                stack.push(a - b);
            }
            case "mul" -> {
                Integer b = stack.pop();
                Integer a = stack.pop();
                stack.push(a * b);
            }
            case "div" -> {
                Integer b = stack.pop();
                Integer a = stack.pop();
                if (0 == b) {
                    flag = false;
                } else {
                    stack.push(a / b);
                }
            }
            default -> { // 数字
                stack.push(Integer.parseInt(t));
            }
        }
        return flag;
    }

    static int priority(String c) {
        switch (c) {
            case "div", "mul":
                return 2;
            case "add", "sub":
                return 1;
            case "(":
                return 0;
            default:
                throw new IllegalArgumentException("不合法的运算符:" + c);
        }
    }
}
